// 思路，在左右区间里随机找个索引，其值作为基准值，把基准值和首位进行交换，从第二位开始，双指针遍历，把小于基准的放在慢指针的位置，
// 最后把首位和慢指针交换，返回确定值的索引即可

// 时间复杂度：最好Onlogn，最坏On2，平局Onlogn
// 空间复杂度：最好Ologn(递归栈深度)，最坏On
// 稳定性：不稳定
// 适用场景，内存友好，较快，通用排序
function quickSort(arr, left = 0, right = arr.length) {
    if (left < right) {
        let pos = partation(arr, left, right)
        quickSort(arr, left, pos - 1)
        quickSort(arr, pos + 1, right)
    }
    return arr
}

function partation(arr, left, right) {
    // 这里需要随机random方法
    let randomIndex = Math.floor(Math.random() * (right - left)) + left;
    let pivot = arr[randomIndex];
    [arr[left], arr[randomIndex]] = [arr[randomIndex], arr[left]];
    let i = left + 1
    for (let j = i; j <= right; j++) {
        if (arr[j] < pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++
        }
    }
    [arr[i - 1], arr[left]] = [arr[left], arr[i-1]];
    return i - 1
}

let arr2 = [6, 2, 1, 3, 7, 5, 4, 8]
console.log(quickSort(arr2))